Trong lý thuyết độ phức tạp tính toán, RP (viết tắt của "randomized polynomial time") là lớp độ phức tạp bao gồm các bài toán sao cho tồn tại máy Turing ngẫu nhiên với các tính chất sau:Nói cách khác, thuật toán cho các bài toán trong RP được phép dùng bit ngẫu nhiên trong quá trình thực thi. Trường hợp duy nhất thuật toán trả về Có là khi lời giải đúng là Có. Tuy nhiên khi thuật toán trả về Không, lời giải đúng có thể là Có hoặc Không.Nếu lời giải đúng là Có thì nếu thực hiện thuật toán n lần độc lập nhau, thì nó trả về Có ít nhất một lần với xác suất ít nhất 1 − 2−n.Trong định nghĩa, số 1/2 được chọn tùy ý. Tập hợp RP không thay đổi nếu 1/2 được thay bằng bất kì hằng số nào nhỏ hơn 1 (hằng số ở đây nghĩa là không phụ thuộc kích thước dữ liệu vào).